package pers.qianyu.month_202102.date_20210215;

import java.util.*;

/**
 * 354. 俄罗斯套娃信封问题
 * https://leetcode-cn.com/problems/russian-doll-envelopes/
 * - 二分做法
 *
 * @author mizzle rain
 * @date 2021年2月15日21:49:45
 */
public class MaxEnvelopes2 {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if (n == 0) return 0;
        Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        int cnt = 0;
        int[] top = new int[n];
        for (int[] x : envelopes) {
            int left = 0, right = cnt;
            while (left < right) {
                int mid = left + right >> 1;
                if (top[mid] >= x[1]) right = mid;
                else left = mid + 1;
            }
            if (cnt == left) cnt++;
            top[left] = x[1];
        }
        return cnt;
    }
}